\section{Problema 2}

\subsection{Introducci\'on}
En este problema, el objetivo es encontrar la mayor \textit{meseta} dentro de una matriz dada. Se define meseta a un área determinada de la matriz, tal que todos los elementos de dicha área son del mismo valor. Un área o meseta de una matriz, es definida por elementos iguales adyacentes entre sí, es decir posiciones contiguas que comparten el mismo valor dentro de la matriz.\\
De esta manera, si una matriz consiste de todos elementos distintos, todas las mesetas de la matriz ser\'ian de tamaño 1. Si todos los elementos de la matriz fueran iguales, en este caso, tendr\'iamos una \'unica meseta de tamaño $n*m$ donde $n$ y $m$ son la cantidad de filas y columnas de la matriz, respectivamente.\\


	   
\subsection{Desarrollo}
Para este problema puntual, se decidi\'o implementar una soluci\'on basada en
una recursi\'on hacia los lados. Nos inclinamos por esta opci\'on ya que es una
forma muy sencilla de ``tirar los problemas hacia adelante'', es decir,
implementar minuciosamente la fuci\'on recursiva, haciendo referencia
puntualmente en el/los casos base y aplicarla bien teniendo en cuenta que la
funci\'on en s\'i hace su trabajo y solo tenemos que enfocarnos en ver hacia
donde la aplicamos. 

Siguiendo esta filosof\'ia nos dimos cuenta que el c\'odigo se
hac\'ia m\'as ameno que otras implementaciones que tambi\'en estuvimos tratando
pero que nos parecieron muy tediosas ( más adelante hare incapie en una de ellas).

No nos fue necesario usar ning\'un tipo de estructura soporte que tuviesemos que
implementar, solo usamos de la librer\'ia de java, la interfaz set implementada
sobre un hashset, el cual está implementada sobre una tabla hash. Decidimos
usar este tipo de set ya que era el m\'as ameno a lo que le quer\'iamos pedir,
pu\'es solamente usabamos el ``set" para guardarnos enteros y preguntar si
est\'an o no. Por este motivo tambi\'en despreciamos su funci\'on hash, pues no
ibamos a tener problemas de ning\'un tipo con coliciones o dem\'as cosas.\\

La idea principal del algoritmo es recorrer la matriz de entrada, desde el
\'indice 0 hasta su longitud total(ver Secci\'on Aclaraciones). Para cada \'indice nos quedamos con su
elemento asociado. Adem\'as nos creamos un conjunto donde iremos poniendo los
\'indices por los que ya pasamos, son meseta y no queremos volver a contar. Esto
se lo pasamos a la funci\'on encargada de encontrar dado un elemento su meseta
en la matriz de donde proviene.

Esta funci\'on funciona de la siguiente manera: dado un elemento de la matriz,
nos movemos hacia los lados, es decir, hacia los cuatro puntos cardinales. Luego
vamos sumando uno si se cumple que en alguna de esas posici\'ones el elemento
asociado es igual al que estamos queriendo evaluar y si anteriormente no
pasamos por ah\'i y ya lo contamos. Adem\'as nos
fijamos que los puntos cardinales por los que estamos tratando sean cooherentes, es decir, no ir a posiciones inv\'alidas de la matriz. 
Entonces lo que hacemos es comprobar esta serie de cosas e ir sumando uno por
cada lado que encuentre un elemento igual. Lo guardamos en nuestro conjunto y
nos desplazamos hacia los lugares donde siga la meseta. 

La recursi\'on terminar\'a cuando lleguemos a un elemento que no est\'e
rodeado por elementos iguales a \'el o que est\'e rodeado de alguno pero que ya
haya sido contado. Para esto usamos el conjunto que nos creamos por cada
elemento. De esta manera terminaremos encontrando su meseta m\'axima. Nos
guardamos ese n\'umero en un acumulador el cual vamos a ir evaluando, preguntando el mayor contra la meseta m\'axima de cada elemento de la matriz.\\

Tuvimos otra idea antes de usar esta \'ultima. Se basaba en un par de
estructuras soporte, como matriz, listas y coordenadas, nada muy complicado,
pero si era muy tedioso de mantenerlas. 

La idea era ir recorriendo la
matriz de entrada y armarnos una \'unica matriz de mesetas que inicialmente
estar\'a formada por unos.
Lo que ibamos haciendo era recorrer la matriz de entrada de izquerda a derecha e ibamos
preguntando si el elemento de al lado era igual al nuestro o al de abajo. 
Entonces en la posici\'on donde estabamos parados y en la de abajo y/o la de
la derecha, le sumabamos uno u 2
seg\'un si los dos lados eran iguales o no. 

El problema que se nos presento fue
mantener esto, ya que teniamos que ir sumando un 1 para todas las posiciones de
esa matriz que en la matriz de entrada tengan el mismo elemento. Adem\'as
tambi\'en se nos hizo muy dif\'icil diferenciar entre mesetas, es decir, si
hab\'ia dos mesetas iguales (misma longitud y mismo elemento) ya que como esta
idea lo que hacia era ir sumando solamente, tomaba
esas dos mesetas como una sola y el resultado era el doble de lo esperado en
este caso. Pudimos resolverlo guardandonos en una lista de listas, una lista
por cada meseta que aparec\'ia, siempre preguntando por el elemento que queremos
sumar si era ``vecino" de alguno de todas las mesetas asociadas a ese n\'umero,
pero finalmente se nos hacia muy largo el codigo y no nos parecio apropiado para
lo que en si el ejercicio ped\'ia.

\newpage

\subsubsection{Aclaraciones}
Si bien en el enunciado del trabajo pr\'actico se habla genericamente de una
``matriz de elementos'', se asume en el algoritmo que tal matriz es de n\'umeros enteros.\\

Aclaramos tambi\'en, que tomamos a la dimensi\'on de la siguiente manera, dado
dos numeros $a$ $b$, $a$ es la cantidad de columnas y $b$ la cantidad de filas.
Esto lo enunciamos, pues los primeros 3 casos del test propuesto por la catedra
ten\'ian de dimension 3 2, nosotros en un principio lo le\'iamos como 3 filas y
2 columnas, pero los resultados no eran los mismo, ya que con esas dimensiones las mesetas eran otras.

Por \'ultimo, aclaramos que hacemos uso del nombre ``matriz'' y trabajamos de
esta forma, pero lo hacemos medianto un vector de tamaño $a$*$b$, la forma de
recorrer este vector hace que pensemos en matriz. Nos pareci\'o una buena forma
de tratar este par\'ametro ya que la lectura y el trato dentro del algoritmo es
ameno, adem\'as de que nos ahorramos de crearnos una clase matriz o ``crearnos''
dicha matriz en el momento de leer los parametros de entra. 

\subsection{Pseudoc\'odigo}
En el archivo \textbf{Ej2.java} podremos encontrar la clase ``Ej2'' con la funcion principal \textit{meseta} y \textit{BuscarCaminos} que es la que se va a encargar de buscar mesetas a los lados.

\begin{algorithm}[H]
\caption{\operL{meseta}{ \vin{filas}{int}, \vin{columnas}{int}, \vin{matriz}{array de ints}}{int}} \begin{algorithmic}[1]\parskip=1mm
\STATE   \textbf{var} maximo $\leftarrow$ 1
\FOR{ i = 0 \textbf{hasta} columnas*filas - 1 }
	\STATE \textbf{var} Conjunto de enteros (vacio) con columnas*filas elementos
	\STATE \textbf{var} meseta $\leftarrow$ la meseta del elemento(matriz[i]) en matriz guardando las posiciones por las que ya pase guardadas en cojunto de enteros.
	\IF{meseta es mas grande que el acumulado que tengo en maximo}
		\STATE maximo $\leftarrow$ meseta		
	\ENDIF 
\ENDFOR
\STATE return maximo

\end{algorithmic}
\end{algorithm}

\begin{algorithm}[H]
\caption{\operL{BuscarCaminos}{ \vin{e}{int}, \vin{indice}{int}, \vin{Matriz}{array de ints},
\vin{columnas}{int}, \vin{filas}{int}, \vin{conjuntoDeIndices}{conjunto de nats}}{int}} \begin{algorithmic}[1]\parskip=1mm
\STATE  \textbf{var} NumeroAcumulado $\leftarrow$ 0
\STATE  \textbf{var} irParaLaDerecha $\leftarrow$ 0
\STATE  \textbf{var} irParaLaIzquierda $\leftarrow$ 0
\STATE  \textbf{var} irParaAbajo $\leftarrow$ 0
\STATE  \textbf{var} irParaArriba $\leftarrow$ 0

\IF{ el indice en la matriz corresponde al mismo elemento que miro y si no conte ya esta posicion antes }
	\STATE Agrego a conjuntoDeIndices el entero indice
	\IF{no puedo ir hacia la derecha porque ya me estoy yendo de la matriz y no estoy parado en la ultima columna}
		\STATE defino irParaLaDerecha a la recursion apuntando al elemento de la derecha.
	\ENDIF
	\IF{no puedo ir para la izquierda y no estoy parado en la primer fila}
		\STATE defino irParaLaIzquierda a la recursion apuntando el elemento de la izquierda.
	\ENDIF
	\IF{no puedo ir para abajo, porque estoy en la ultima fila}
		\STATE defino irParaAbajo como la recursion de apuntar el elemento hacia uno mas abajo.
	\ENDIF
	\IF{no puedo ir para arriba, porque estoy en la primer fila}
		\STATE defino irParaArriba como la recursion de apuntar el elemento uno mas hacia arriba.
	\ENDIF

		\STATE numeroAcumulado $\leftarrow$ 1 + recursion hacia la derecha + recursion hacia la izquierda + recursion hacia abajo + recursion hacia arriba
\ENDIF 
\STATE return numeroAcumulado

\end{algorithmic}
\end{algorithm}

\newpage
\subsection{Complejidad}

 La complejidad de este algoritmo parece ser, a priori un poco complicada de ver, pero se facilita si lo seguimos paso a paso y pensamos un poco que es lo que estamos buscando.
 
 En \textit{meseta} vamos a recorrer la matriz de entrada. Esta
 funci\'on solamente tiene un for que va a iterar cada uno de los elementos de
 la matriz de entrada y adem\'as nos crearemos un  conjunto de tamaño igual al
 tamaño de la entrada. Esto es lo mas significativo del algoritmo, ya que luego
 lo \'unico que tenemos es un if y una comparaci\'on de enteros que tiene
 complejidad constante. 
 
 Sea T(n) la funci\'on que representa la
 complejidad de este algoritmo. Tenemos que T(n), con n = $a$*$b$, va a ser
 igual a $a$*$b$ por la creaci\'on de un conjunto + $a$*$b$ que es la
 complejidad asint\'otica de la funci\'on \textit{buscarCaminos}. 
 
 Pasando en limpio tenemos
 que T(n) = $a$*$b$ + $a$*$b$ = 2*$a$*$b$. Luego usando la definici\'on de $O$,
 tenemos que O(2*$a$*$b$) $\in$ O($a$*$b$) pues existe un c mayor a 0 tal que f($a$,$b$) = 2*$a$*$b$ $\leq$ C*g($a$,$b$) = C*$a$*$b$, con c$\geq$ 2.
 
 En \textit{buscarCaminos} tenemos la parte, si se quiere, mas complicada de
 calcular, ya que es la funci\'on principal recursiva que utilizaremos para
 resolver nuestro problema. 
 
 Lo primero que tenemos es un if, lo mas importante
 de este es la parte en donde preguntamos si un elemento est\'a contenido en el
 conjunto que venimos manteniendo por cada elemento. La complejidad de esto  se
 basa en el tamaño del conjunto creado que es $a$*$b$. Luego los dem\'as
 booleanos que pertenecen al if son constantes ya que son comparaciones entre elementos enteros.
 
Mas dentro del algoritmo tenemos otras condiciones que al igual que antes,
contienen comparaciones entre enteros, pero seg\'un el resultado de cada if la
variable \textit{numeroAcumulado} se calcula de distintas formas, es ahi donde
hacemos uso de la recursion. En si esta recursi\'on lo que va a hacer es
recorrer la matriz seg\'un los resultados de los ifs anteriores. Entonces
podemos concluir que dado un elemento, el algoritmo \textit{buscarCaminos}
recorrer\'a toda la matriz en su peor caso (cuando la matriz tenga todos sus
elementos iguales).

Entonces si tomamos a T(n) como la funci\'on que representa la complejidad de
esta. T(n), con n = a*b, va a ser igual a $a$*$b$ por la b\'usqueda pues
utilizamos \textit{contains}, un m\'etodo de HashSet donde nos permite afirmar
si un elemento se encuentra en un conjunto en un tiempo lineal con respecto a la
capacidad del conjunto en su peor caso  + lo
que nos cuesta hacer recursi\'on sobre los siguientes elementos, esto est\'a en
el orden de $a$*$b$, ya que a lo sumo, por cada elemento
(derecha,izquierda,arriba,abajo) vamos a recorrer toda la matriz. 

Luego pasando en limpio tenemos que T(n) = a*b + a*b = 2*a*b y por el mismo
argumento que utilizamos para la funci\'on anterior obtenemos que T(n) = 2*a*b
$\in$ O(a*b), siendo $a$ las columnas de la matriz de entrada y $b$ las filas.

En resumen: 

\begin{center}
    \begin{tabular}{ | p{17cm} |}
	\hline
	Sean \textbf{M} la matriz de entrada, \textbf{a} y \textbf{b} las dimensiones de la matriz.
	\begin{itemize}
	  \item \textit{meseta}: recorrer la matriz de entrada  llevar\'a complejidad
	  \textbf{O($a$*$b$)} $+$ \textbf{O($a$*$b$)} por la creaci\'on de un conjunto
	  de tamaño ($a$*$b$).
				Adem\'as como \textbf{O($a$*$b$)} + \textbf{O($a$*$b$)} $\in$
				\textbf{O($a$*$b$)} a la conclusi\'on que llegamos es que la complejidad
				asint\'otica es \textbf{O($a$*$b$)}
	  \item \textit{buscarMeseta}: aplicar esta funci\'on para cada elemento,
	  teniendo en cuenta la complejidad del if mas grande (O($a$*$b$) por la
	  b\'usqueda de un elemento en un conjunto) y la complejidad en s\'i de esta
	  funci\'on, que se encarga de, dado un elemento recorrer la matriz preguntando
	  si el elemento donde estamos parados es igual al que queremos evaluar
	  (O($a$*$b$)) por ser la dimensi\'on de la matriz y luego, como en el punto
	  anterior tenemos que \textbf{O($a$*$b$)} + \textbf{O($a$*$b$)} $\in$
	  \textbf{O($a$*$b$)}. Esta \'ultima es la complejidad de este algoritmo.
	\end{itemize}
	En conclusi\'on:
	Nuestras funciones \textit{meseta} y \textit{buscarCaminos} son de orden
	\textbf{O($a$*$b$)} y como la segunda se ejecuta por cada iteraci\'on de la
	primera, es decir, por cada elemento que recorre \textit{meseta} aplicamos
	\textit{buscarCaminos} podemos concluir que  la complejidad asint\'otica del
	algoritmo que resuelve el ejercicio 2 es: \\
	\textbf{O(($a$*$b$)*($a$*$b$))}.
	 \\ \hline
    \end{tabular}
\end{center}


\subsection{Tests}

Los test sobre los cuales nos basamos, fueron elegidos de una forma particular
para cada caso. 

Para mostrar el mejor caso, nos dimos cuenta que,
como pensamos el algoritmo, basta con tener una matriz con elementos distintos
o que, al ser iguales, no sean vecinos ya que en estos casos lo m\'inimo que se
tiene que hacer para averiguar la meseta, es recorrer toda la matriz por lo
menos una vez. Por lo tanto la dimensi\'on en si no importa, mientras las
mesetas de las matrices a implementar sean todas iguales a 1.

Para los casos de peor rendimiento, volvimos a mirar el algoritmo y llegamos a
la conclus\'ion de que los casos patol\'ogicos, se formaban mayormente cuando la
meseta m\'axima representa a la dimension de la matriz con la que estamos
tratando, es decir, una matriz con todos sus elementos iguales y en las
matrices donde las mesetas sean iguales, es decir dos mesetas de cantidad x,
mesetas circulares por ejemplo, que se conformen solamente o parcialmente por el
"contorno `` de la matriz.
Esas fueron algunas de las ideas para poder corroborar la correctitud de nuestro algoritmo.

\begin {figure} [H]
\begin {center}
\includegraphics[width=12cm]{./graficos/Grafico-mejor-caso.png}
\caption{Grafico que representa la cantidad de iteraciones en funcion de la dimension de una matriz}
\end {center}
\end{figure}
Este gr\'afico nos muestra como var\'ia la cantidad de iteraciones del primer
for sumado a la cantidad de recursiones que usamos para resolver cada matriz de
dimensiones x*x y que tiene todos numeros distintos, es decir, de meseta 1.
Estos casos serian los mas sencillos, ya que el algoritmo deber\'ia recorrer la
matriz una vez para encontrar el m\'aximo.

\begin {figure} [H]
\begin {center}
\includegraphics[width=12cm]{./graficos/Grafico-Comparacion-teorico-practico.png}
\caption{Grafico que representa la cantidad de iteraciones en funcion de la dimension de una matriz}
\end {center}
\end {figure}
Este Gr\'afico representa, como el anterior, la cantidad de iteraciones del for
y la cantidad de recursiones que tenemos que hacer para resolver matrices de x*x
cuando la meseta es x*x, es decir, cuando la meseta esta conformada por todos
los elementos de la matriz. Tambi\'en lo comparamos con nuestra complejidad
te\'orica, para esto usamos la funcion x*x, donde x es la dimension de la matriz
a evaluar. 

Lo que podemos observar es que las dos funciones son muy parecidas( peor caso y caso teorico, o sea la complejidad calculada) y var\'ian, es de esperar ya que nuestra complejidad asintotica es O($m$*$m$) con $m$ = $a$*$b$, donde $a$ es la cantidad de columnas y $b$ cantidad de filas y en si el algoritmo recorre una vez mas estas matrices, pero siempre est\'a incluido en la complejidad asintotica calculada (se explica bien en la parte de complejidad), esto nos da un indicio de que la complejidad calculada para nuestro algoritmo se corresponde con la complejidad en su peor caso.

Estos casos son los mas complicados, si se quiere, pues nuestro algoritmo recorre por cada elemento de la matriz, toda la matriz buscando la meseta asociada a cada elemento.

\begin {figure} [H]
\begin {center}
\includegraphics[width=12cm]{./graficos/Comparacion-de-rendimientos.png}
\caption{Comparacion de rendimientos, entre mejores casos y peores casos}
\end {center}
\end{figure}
Finalmente tenemos el gr\'afico comparando las dos situaciones, los mejores
casos y los peores casos en funci\'on de sus dimensiones. 

Esto tambi\'en nos
permite ver como en los peores casos nuestro algoritmo presetenta una especie de
media parabola, corroborando a simple vista que en peor caso el algoritmo toma
forma de una funcion cuadr\'atica en funci\'on de la dimensi\'on.
Esto lo hacemos para mostrar como puede variar el tiempo, en funci\'on de que
tan variada es la matriz, en el medio de esas dos funciones caeran las demas
matrices aleatoriamente creadas sin intencionalidad.

\subsection{Conclusiones}

Este problema se presento como algo sencillo de hacerlo al principio, aunque nos topamos con la dificultad de tratar de implementar una idea no muy elegante , pero luego pudimos hacer un algoritmo basado en la recursion, que nos parecio lo mas corto y sencillol de poder explicar.

Los test que pudimos hacer nos dieron la idea de que, los casos a probar eran
m\'as interesantes si los hac\'iamos a mano que tratar de generar matrices
aleatorias o siguiendo algun patr\'on. 

Adem\'as de confirmarnos que la complejidad
pedida se cumplia en cada caso con la calculada en base a nuestro algoritmo.
En s\'i, aplicar recursi\'on en muchos casos puede ser algo tedioso de seguir y
m\'as si no se implementa y se plasma en un c\'odigo claro y simple. En nuestro
caso pudimos hacerlo, creemos de la mejor manera, porque en si el problema no
presentaba muchas m\'as dificultades m\'as que la complejidad pedida o algunas
problemas m\'inimos de l\'imites de la matriz, pero es una forma muy sencilla de
pensar el problema sabiendo que si nuestra funci\'on recursiva est\'a bien
implementada es solo ver hacia donde y hacia que cosas aplicarle esa
recursi\'on, olvidandonos un poco que es lo que va a hacer sobre donde lo
apliquemos, pero si sabiendo que lo va a hacer bien como lo hab\'amos pensado.


